Dr. J's Maths.com
Where the techniques of Maths
are explained in simple terms.

Networks and Graph Theory - Finding the shortest path.
Test Yourself 1.


 

Remember:

To find the shortest path between two given vertices, we use Dijkstra's algorithm.

1. The network shown at the left has 6 nodes shown in blue.

The weights are shown in pink.

Find the shortest path from A to F and calculate its length.

Answer.Minimum path is A-C-E-G
and minimum weight is 23.
2. The network shown at the left has 7 nodes shown in blue.

The weights are shown in pink.

Find the shortest path from A to G and calculate its length.

Answer.Minimum path is A-B-E-F
and minimum weight is 6.
3. The network shown at the left has 8 nodes shown in blue.

The weights are shown in pink.

Find the shortest path from A to C and calculate its length.

Answer.Minimum path is A-B-D-C
and minimum weight is 14.
4. The network shows the roads connecting nine warehouses for a major supermarket chain and they are labelled A to I.

The weights on the edges are the average travel times (in hours) between the adjacent warehouses.

What is the shortest travel time from warehouse B to warehouse H?
Answer.B-C-F-G-H with a minimum time of 36 hours.
5. The diagram shows seven key areas of a city and the network of public transport links between them.

The costs of travelling between those key places (in dollars) is also shown on the edges.

Calculate the minimum cost for a visitor to travel from the Guest House to the Harbour.

Answer.Minimum path is GH-M-S-G-H
and minimum cost is $14.
6. Calculate the minimum path from B to D.
Answer.Minimum path is B-A-C-E-D
and it is of length 13.
7. The network summarised in the diagram below shows a cross-section of an insect nest I found in a nearby park. It had been cut in two horizontally.

The lines shows the paths along which the insects travelled and the numbers show the lengths of each path in centimetres.

Find the shortest path from the entrance at point A to the exit at point H and hence calculate the shortest distance from A to H.

Answer.Minimum path is A-D-J-F-H
and it is of length 10.